package com.hyper_yang.algorithmRecord;

// 寻找重复数
public class LeetCode_287 {
//    给定一个包含 n + 1 个整数的数组 nums ，
//    其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
//    假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
//    你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
    /*
        规律: 以 target为界，对于比 target小的数 i，数组中所有小于等于 i的数，最多出现 1次，总个数不会超过 i
        对于比 target大的数 j,如果每个元素都只出现一次，那么所有小于等于 j的数，是 j个,而如果 target重复出现，总数就一定大于j
     即： 对于 1~n的某个数 i，如果记数组中所有小于等于他的所有元素个数为count[i],
        则 i ∈ [1, target-1] -> count[i] <= i
          i ∈ [target, n] -> count[i] > i
     */

    // 方法一: 二分查找，查找 1~n的自然数序列，寻找 target
    public static int findDuplicate1(int[] nums) {
        int left = 1;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) >> 1;

            int count = 0;
            for (int i : nums) {
                if (i <= mid) count++;
            }

            if (count <= mid) left = mid + 1;
            else right = mid;

            if (left == right) return left;
        }

        return -1;
    }

    // 方法二: 快慢指针 循环检测法
    public static int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (fast != slow);

        int before = 0, after = slow;
        while (before != after) {
            before = nums[before];
            after = nums[after];
        }

        return before;
    }

    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{1, 3, 4, 2, 2}));
        System.out.println(findDuplicate(new int[]{3, 1, 3, 4, 2}));
        System.out.println(findDuplicate(new int[]{3, 3, 3, 3, 3}));
        System.out.println(findDuplicate(new int[]{7, 9, 7, 4, 2, 8, 7, 7, 1, 5})); // answer: 7
    }
}
